package array;

/**
 * 给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。
 * <p>
 * 由于答案可能会很大，请你将结果对 10^9 + 7 取余后返回。
 * <p>
 * 示例 1：
 * 输入：arr = [1,3,5]
 * 输出：4
 * 解释：所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
 * 所有子数组的和为 [1,4,9,3,8,5].
 * 奇数和包括 [1,9,3,5] ，所以答案为 4 。
 * <p>
 * 示例 2 ：
 * 输入：arr = [2,4,6]
 * 输出：0
 * 解释：所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
 * 所有子数组和为 [2,6,12,4,10,6] 。
 * 所有子数组和都是偶数，所以答案为 0 。
 * <p>
 * 示例 3：
 * 输入：arr = [1,2,3,4,5,6,7]
 * 输出：16
 * <p>
 * 示例 4：
 * 输入：arr = [100,100,99,99]
 * 输出：4
 * <p>
 * 示例 5：
 * 输入：arr = [7]
 * 输出：1
 *
 * @author Jisheng Huang
 * @version 20250522
 */
public class NumOfSubarrayWithOddSum_1524 {
    /**
     * @param arr the given array
     * @return number of all the cases for the sum is odd
     */
    public static int numOfSubarrays(int[] arr) {
        int MOD = 1000000007;
        int odd = 0;
        int even = 1;
        int subarrays = 0;
        int sum = 0;
        int length = arr.length;

        for (int i = 0; i < length; ++i) {
            sum += arr[i];
            int addsOn = sum % 2 == 0 ? odd : even;
            subarrays = (subarrays + addsOn) % MOD;

            System.out.println(subarrays);

            if (sum % 2 == 0) {
                ++even;
            } else {
                ++odd;
            }
        }

        return subarrays;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5};
        System.out.println(numOfSubarrays(arr));

        arr = new int[]{2, 4, 6};
        System.out.println(numOfSubarrays(arr));

        arr = new int[]{1, 2, 3, 4, 5, 6, 7};
        System.out.println(numOfSubarrays(arr));

        arr = new int[]{100, 100, 99, 99};
        System.out.println(numOfSubarrays(arr));

        arr = new int[]{7};
        System.out.println(numOfSubarrays(arr));
    }
}